/**********************
dp[i][j]: 和并i到j的最小代价
w[i][j]: i到j的石子总代价
一般递推式
dp[i][j] = {
    0, i==j
    w[i][j]+min(dp[i][k]+dp[k+1][j]), i<=k<j
}
采用四边行优化的递推式
s[i][j]: 表示合并第i到j堆石子时的最优策略中最后一次合并的最小k值
dp[i][j] = {
    0, i==j
    w[i][j]+min(dp[i][k], dp[k+1][j]), s[i][j-1]<=k<=s[i+1][j]
}
**********************/
#include <stdio.h>

int const MPN = 50000; //最大石子堆数
int const MCOST = 1e9+7; //最大dp值
int dp[MPN][MPN];
int w[MPN][MPN];
int s[MPN][MPN];
int piles[MPN]; //记录各堆石子数
int n = 0; 

void dp_min_cost(void) {
    for(int i=0; i<n; i++) {
        w[i][i] = piles[i];
    }
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            w[i][j] = w[i][j-1]+piles[j];
        }
    }
    for(int i=1; i<n; i++) {
        dp[i-1][i] = w[i-1][i];
        s[i-1][i] = i-1; 
    }
    for(int gap=2; gap<n; gap++) {
        for(int i=0, j=i+gap; j<n; i++,j++) {
            dp[i][j] = MCOST;
            for(int k=s[i][j-1]; k<=s[i+1][j]; k++) {
                int cur = dp[i][k]+dp[k+1][j];
                if(cur<dp[i][j]) {
                    dp[i][j] = cur;
                    s[i][j] = k;
                }
            }
            dp[i][j] += w[i][j];
        }  
    }
}
int main(void) {
    while(true) {
        scanf("%d", &n);
        if(!n) break;
        for(int i=0; i<n; i++) {
            scanf("%d", &piles[i]);
        }
        dp_min_cost();
        printf("%d\n", dp[0][n-1]);
    }
    return 0;
}


